// 52.N皇后2
package Leetcode_Second_Brush;

import java.util.ArrayList;

public class Solution052 {
    int result = 0;

    public int totalNQueens(int n) {
        boolean[] column = new boolean[n];
        boolean[] ltTorb = new boolean[2 * n - 1];
        boolean[] rtTolb = new boolean[2 * n - 1];
        backTrace(n, new ArrayList<>(), 0, column, ltTorb, rtTolb);
        return result;
    }

    private void backTrace(int n, ArrayList<int[]> list, int cur, boolean[] column,
            boolean[] ltTorb, boolean[] rtTolb) {
        if (cur == n) {
            result++;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (column[i] || ltTorb[cur + i] || rtTolb[cur - i + n - 1])
                continue;
            list.add(new int[] { cur, i });
            column[i] = true;
            ltTorb[cur + i] = true;
            rtTolb[cur - i + n - 1] = true;
            backTrace(n, list, cur + 1, column, ltTorb, rtTolb);
            list.remove(list.size() - 1);
            column[i] = false;
            ltTorb[cur + i] = false;
            rtTolb[cur - i + n - 1] = false;
        }
    }

}
